package leetcode.array_sort;

/**
 * @author: Oliver
 * @time: 2020/6/1/22:02
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * <p>
 * 示例:
 * <p>
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * <p>
 * 说明:
 * <p>
 * 必须在原数组上操作，不能拷贝额外的数组。
 * 尽量减少操作次数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/move-zeroes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 分析：方案一；借助其他数组，遍历循环存放非零元素，然后再次遍历辅助数组，将其他位置设为0，进行返回。  时间复杂度，空间复杂度都为O(N)
 * 方案二 定义一个变量k 使得 [l，k) 都是非零元素，[k,r]都是0
 * 定义i 使得 i指向下一个需要判断的元素。 时间复杂度 O(N) 空间复杂度 O(1)
 */
public class Solution283 {

    public static void moveZeroes(int[] nums) {
        move(nums, 0, nums.length - 1);
    }

    private static void move(int[] arr, int l, int r) {
        int k = l;// 符合语意 arr[ l, k）存放非零元素 当前数组大小为0
        for (int i = 0; i <= r; i++) {
            if (arr[i] != 0) {
                arr[k] = arr[i];
                k++;//维护k，使得k满足定义语意
            }
        }
        for (int i = k; i <= r; i++) {
            arr[i] = 0;
        }
        for (int i = l; i <= r; i++) {
            if (i == l) {
                System.out.print("[" + arr[i] + ",");
            } else if (i == r) {
                System.out.println(arr[i] + "]");
            } else
                System.out.print(arr[i] + ",");
        }
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes(nums);
    }
}
